public class code3 {

//    牛客 top 101 树的右视图

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * @param preOrder int整型一维数组 先序遍历
     * @param inOrder int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] preOrder, int[] inOrder) {

        // 将问题分为两部分解决
        // 首先通过两个遍历得到的数组创建出一个新的 树
        // 之后再来解决最右元素的问题

        // write code here
        ArrayList<Integer>  res = new ArrayList<>();
        Queue<TreeNode>  queue = new LinkedList<>();

        TreeNode  root = CreateTree(preOrder, inOrder);

        // 这里通过队列和数组的形式实现对于最右侧数据的存储操作
        // 同样的还是根据先序遍历的思想。根、左、右
        // 按照上面的存储顺序，在队列中，最后一个位置的元素永远是该子树位置的最右侧子树
        // 可以说通过一个数 n 来进行记录
        // 在这里将 n 的值进行递减操作，最终在顺序表中存储到的值就是最右侧的数据
        // 最后返回这个顺序表即可

        queue.add(root);
        if(preOrder.length==0||inOrder.length==0) return new int[0];
        while (!queue.isEmpty()) {
            int n = queue.size();
            while(n-->0){
                TreeNode temp = queue.poll();
                //最右元素
                if(n == 0)
                    res.add(temp.val);
                if(temp.left != null)
                    queue.offer(temp.left);
                if(temp.right != null)
                    queue.offer(temp.right);
            }
        }
        int n = res.size();
        int[] array = new int[n];
        for(int i =0;i<n;++i){
            array[i] =res.get(i);
        }
        return array;
    }
    public TreeNode CreateTree (int[] pre, int[] in) {
        // write code here
        int n = pre.length;
        int m =  in.length;
        if (n == 0 || m == 0) return null;
        TreeNode root = new TreeNode(pre[0]);
        for (int i = 0; i < in.length; i++) {
            if (pre[0] ==  in[i]) {
                root.left = CreateTree(Arrays.copyOfRange(pre, 1, i + 1),
                        Arrays.copyOfRange( in, 0, i));
                root.right = CreateTree(Arrays.copyOfRange(pre, i + 1, pre.length),
                        Arrays.copyOfRange( in, i + 1,  in.length));
                break;
            }
        }
        return root;
    }
}
